//
// Created by PC on 2024/2/26.
//


#include "arrUtil.h"

using namespace std;

vector<int> merge(vector<int> v1,vector<int>v2)
{
    vector<int> t;
    int i1=0,i2=0;
    while(i1<v1.size() && i2<v2.size())
    {
        if(v1[i1]<=v2[i2])
        {
            t.push_back(v1[i1]);
            ++i1;
        }else
        {
            t.push_back(v2[i2]);
            ++i2;
        }
    }
    for(;i1<v1.size();++i1)
        t.push_back(v1[i1]);
    for(;i2<v2.size();++i2)
        t.push_back(v2[i2]);
    return t;
}

vector<int> mergeSort(vector<int> v)
{
    if(v.size()>1)
    {
        vector<int> left,right;
        int m = v.size()/2;
        for (int i = 0; i < m; ++i)
            left.push_back(v[i]);
        for (int i = m; i < v.size(); ++i)
            right.push_back(v[i]);
        return merge(mergeSort(left),mergeSort(right));
    }
    return v;
}


int main()
{
    vector<int> arr={9,7,4,2,6,5,1,0,5};
    randVector(arr,1000);
    vector<int> ret = mergeSort(arr);
//    printVector(ret);
    cout<<checkSortVector(ret);
    return 0;
}